import java.util.Stack;

//逆波兰表达式
public class Test {
    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if(!isOpertion(tokens[i])){
                String x = tokens[i];
                stack.push(Integer.valueOf(x));
            }else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch (tokens[i]){
                    case "+":
                        stack.push(num2 + num1);
                        break;
                    case "-":
                        stack.push(num2 - num1);
                        break;
                    case "*":
                        stack.push(num2 * num1);
                        break;
                    case "/":
                        stack.push(num2 / num1);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOpertion(String s){
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            return true;
        }
        return false;
    }



    //有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i<s.length(); i++){
            char ch = s.charAt(i);
            //左括号
            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }else {//右括号
                if(stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if(top == '(' && ch == ')'  || top == '{' && ch == '}' || top == '[' && ch == ']'){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }


    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }



    //判断入环点
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //如果再循环结束后fast = null 或者 fast.next =null
        if(fast == null || fast.next == null){
            return null;
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }

        return fast;

    }



    //移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }

        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = pre.next;
                cur = cur.next;
            }
            //单独判断头节点
        }
        if(head.val == val){
            //删除头节点
            head = head.next;
        }
        return head;
    }


    //反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode cur = head.next;
        head.next = null;


        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //链表中间节点
    public ListNode middleNode(ListNode head) {
        ListNode fast =head;
        ListNode slow =head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //合并两个有序列表
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(100);
        ListNode tmpHead = newHead;

        while(headA != null && headB != null){
            if(headA.val < headB.val){
                tmpHead.next = headA;
                headA = headA.next;
            }else{
                tmpHead.next = headB;
                headB = headB.next;
            }
            tmpHead =tmpHead.next;
        }

        if(headA != null){
            tmpHead.next = headA;
        }

        if(headB != null){
            tmpHead.next = headB;
        }

        return newHead.next;

    }

    //链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;

        ListNode ha = headA;
        ListNode hb = headB;

        while(ha != null){
            lenA++;
            ha = ha.next;
        }

        while(hb != null){
            lenB++;
            hb = hb.next;
        }
        ha = headA;
        hb = headB;

        int size = lenA - lenB;
        if(size < 0){
            ha = headB;
            hb = headA;
            size = lenB - lenA;
        }

        //先走size步
        while(size != 0){
            ha = ha.next;
            size--;
        }

        while(ha != null && hb !=null){
            if(ha == hb){
                return ha;
            }
            ha = ha.next;
            hb = hb.next;
        }
        return null;
    }
}
